1. Field of the Invention
The present invention is generally related to systems, circuits, and methods for processing images of written or printed characters to recognize such characters and, more particularly, related to systems, circuits, and methods for extracting connected component features from images.
2. Description of the Related Art
For character recognition, connected component features are extracted from images of the input characters and, based on these features, classification is performed. For purposes of the description herein, the image of the character to be recognized is composed of pixels that are dark relative to the balance of the pixels in the image. For convenience of illustration and explanation, dark and light pixels will be referred to herein as black and white pixels, respectively. A “connected component” is a group of connected black pixels surrounded by white pixels. A single isolated black pixel is also counted as a “connected component.” To achieve high performance in classification, connected component feature extraction plays a significant role.
Hereinafter, classification of handwritten digits is described as an example of character recognition. Since the strokes of digits make up the basis of other kinds of characters, techniques for handwritten digit classification can be applied to other character recognition as well.
FIG. 1A shows an example of a normalized 20×20 handwritten digit image matrix, in which the pixels in row X and column Y are each referred to as (X, Y). Each black pixel is represented by “1,” and each white pixel is represented by “0.” An exemplary feature extraction process on this image matrix, which the inventors proposed in the paper entitled “A Current-mode CNN Feature Extractor for Handwritten Digit Classification,” is described below. The paper was released in the Proceedings of 1999 Chinese Conference on Neural Network and Signal Processing (CCNNSP) in December 1999.
First, the number of connected components is counted for each of the 20 columns in the horizontal direction. The result of this counting is shown in FIG. 1B. For example, column 3 has only one connected component from (15, 3) to (18, 3), column 4 has three connected components: the first one is from (6, 4) to (8, 4); the second one is (14, 4); and the third one is (19, 4), and so forth. Succeedingly or concurrently, the number of connected components is counted for each of the 20 rows in the vertical direction. The result of this counting is shown in FIG. 1C. For example, row 2 has only one connected component from (2, 8) to (2, 11), row 3 has two connected components: the first one is (3, 7); and the second one is from (3, 12) to (3, 13), and so forth.
Because the number of strokes of handwritten digits is relatively low, the number of connected components in any row or column is usually four or less. This is the reason for which the results shown in FIGS. 1B and 1C have four bits from Bit-0 to Bit-3 for each of the 20 columns and rows. Here, Bit-0 is redundant in either the horizontal or vertical direction. This is because Bit-0 is always “1” within the area of a normalized image of one digit and thus does not provide any classification information. Bit-0 is therefore eliminated, leaving a 3×20-bit connected component feature acquired for each of the horizontal and vertical directions.
Further, the number of connected components is counted in one diagonal direction. In a positive diagonal direction from upper-left to lower-right, two connected component are found at (5, 5) and (12, 12). Since, as described above, the first bit is redundant and thus can be eliminated, a 3-bit connected component feature (1, 0, 0) is acquired for the positive diagonal direction, as shown in FIG. 1D. Succeedingly or concurrently, the number of connected components is counted in the other diagonal direction. In this negative diagonal direction, two connected components are found at (18, 3) and at (6, 15). With the elimination of the first bit, a 3-bit connected component feature (1, 0, 0) is acquired for the negative diagonal direction, as shown in FIG. 1E.
The 60-bit feature acquired for each of the horizontal and vertical directions can be compressed into a 40-bit feature as follows. In the 3×20-bit feature of each of FIGS. 1B and 1C, if the next higher bit is “1,” the immediate lower bit is also “1” for every column or row. Compression of the feature information is performed based on this correlation. An aspect of this compression into fewer bits is illustrated in FIG. 2A, using a 2×2-bit matrix as an example. To implement this idea for a 3×2-bit matrix, a logic circuit including three NOR gates and three Exclusive-OR gates connected as shown in FIG. 2B can be employed. After processing by the circuit of FIG. 2B, the 3×20-bit feature of FIG. 1B is compressed into a 3×10-bit feature, as shown in FIG. 3A. Similarly, the 3×20-bit feature of FIG. 1C is compressed into a 3×10-bit feature, as shown in FIG. 3B.
In FIG. 2B, each of the inputs A, B, and C represents Bit-1, Bit-2, and Bit-3 of FIGS. 1B/1C, respectively. The first output (O0, O1, O2) is calculated when Bit-1 at column 1, Bit-1 at column 2, Bit-2 at column 1, Bit-2 at column 2, Bit-3 at column 1, and Bit-3 at column 2 are input to the circuit as A0, A1, B0, B1, C0, C1, respectively. The second output (O0, O1, O2) is calculated when Bit-1 at column 3, Bit-1 at column 4, Bit-2 at column 3, Bit-2 at column 4, Bit-3 at column 3, and Bit-3 at column 4 are input to the circuit as A0, A1, B0, B1, C0, C1, respectively. By continuing the calculation process in this manner, ten outputs (O0, O1, O2), i.e., a 3×10-bit feature, is acquired.
To compensate for a loss of information during the above compression process, seven other bits are added to the feature vector, as shown in FIGS. 3A and 3B. These 7 bits are acquired by counting the number of connected components in the 3×20-bit feature matrix. For example, in FIG. 3A, row A has one connected component from column 4 to 15, and row B has two connected components from column 4 to 9 and from 12 to 14.
Finally, a 40-bit feature vector is acquired for the horizontal and one diagonal directions, by including the 3×10-bit feature of FIG. 3A, the 7-bit feature of FIG. 3A, and the 3-bit feature of FIG. 1D. Similarly, another 40-bit feature vector is acquired for the vertical and the other diagonal directions, by including the 3×10-bit feature of FIG. 3B, the 7-bit feature of FIG. 3B, and the 3-bit feature of FIG. 1E. The total 80-bit feature vector is used in classification in the next stage.
The connected component features are relatively invariant against transforming or rotating of the handwritten character, and therefore enable the classification with high performance. In the above example, the connected component feature extraction is performed upon acquiring the 4×20-bit matrices of FIGS. 1B and 1C, the 4-bit features a part of which becomes the 3-bit features of FIGS. 1D and 1E, and the 7-bit features shown in FIGS. 3A and 3B.
A neural network is currently used to perform connected component feature extraction. However, since neural networks are relatively complex and tend to consume a large amount of electrical power, a feature extractor with a simpler structure is desired, especially for portable use of character recognition. Further, it is desired to accelerate a processing speed of the feature extractors.